package LinkedList;//给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, ... 。
//
// 每个节点都可能有下一个更大值（next larger value）：对于 node_i，如果其 next_larger(node_i) 是 node_j.
//val，那么就有 j > i 且 node_j.val > node_i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0
// 。 
//
// 返回整数答案数组 answer，其中 answer[i] = next_larger(node_{i+1}) 。 
//
// 注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其头节点的值为 2，第二个节点值为 1，第三个节点值为 5 。 
//
// 
//
// 示例 1： 
//
// 输入：[2,1,5]
//输出：[5,5,0]
// 
//
// 示例 2： 
//
// 输入：[2,7,4,3,5]
//输出：[7,0,5,5,0]
// 
//
// 示例 3： 
//
// 输入：[1,7,5,1,9,2,5,1]
//输出：[7,9,9,9,0,5,0,0]
// 
//
// 
//
// 提示： 
//
// 
// 对于链表中的每个节点，1 <= node.val <= 10^9 
// 给定列表的长度在 [0, 10000] 范围内 
// 
// Related Topics 栈 数组 链表 单调栈 👍 173 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class nextLargerNodes {
    public int[] nextLargerNodes1(ListNode head) {
        /**
         * 将链表的值转化为list 利用栈
         * 同 739 每日温度
         * */

        //将链表的值保存到集合中
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }

        //利用栈来解决
        int[] res = new int[list.size()];
        Stack<Integer> stack = new Stack<>(); // 保存元素下标
        for (int i = 0; i < list.size(); i++) {
            while(!stack.isEmpty() && list.get(stack.peek()) < list.get(i)){
                int index = stack.pop();
                res[index] = list.get(i);
            }
            stack.push(i);
        }
        return res;

    }

    public int[] nextLargerNodes(ListNode head) {
        /**
         * 不转化为list 结合栈
         * */
        Stack<Integer> stack = new Stack<>(); // 保存元素下标
        List<Integer> list = new ArrayList<>();  //
        int index = 0;
        for (ListNode node = head; node != null; node = node.next) {

            while(!stack.isEmpty() && node.val > list.get(stack.peek())){
                int i = stack.pop();  //栈中小值的下标
                list.set(i, node.val);
            }
            stack.push(index++);
            list.add(node.val);
        }
        //当前还在栈里的下标位置，说明没有比他大的，置为0
        for (int i : stack) {
            list.set(i, 0);
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return  res;

    }
}
//leetcode submit region end(Prohibit modification and deletion)
